The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
An Autonomous System (AS) is a network or group of networks under common administration and with common routing policies. A typical example of autonomous system is a network administered and maintained by an Internet Service Provider (ISP). Customer networks, such as universities or corporations, connect to the ISP, and the ISP routes the network traffic originating from the customer networks to network destinations that may be in the same ISP or may be reachable only through other ISPs.
Usually, an autonomous system comprises network elements that are established on the edge of the system, and that serve as the system's ingress and egress points for network traffic. These network elements often, but not always, are routers and are referred to as Provider Edge (PE) network elements or as Autonomous System Border Routers (ASBRs). An autonomous system may also include other network elements that are not used as ingress or egress points for network traffic, and these network elements are referred to as provider network elements. Similarly, a customer network may comprise network elements that are established on the edge of the network, and that are referred to as Customer Edge (CE) network elements.
In order to facilitate the routing of network traffic through one or more autonomous systems, the network elements of the autonomous systems need to exchange routing information to various network destinations. Border Gateway Protocol (BGP) is an exterior gateway protocol (EGP) that is used to exchange routing information among network elements (usually routers) in the same or different autonomous systems. A computer host that executes a BGP process is typically referred to as a BGP host or a BGP device.
In order to exchange BGP routing information, two BGP hosts, or peers, first establish a transport protocol connection with one another. Initially, the BGP peers exchange messages to open a BGP session, and, after the BGP session is open, the BGP peers exchange their entire routing information. Thereafter, only updates or changes to the routing information are exchanged, or advertised, between the BGP peers. The exchanged routing information is maintained by the BGP peers during the existence of the BGP session.
The BGP routing information includes the complete route to each network destination that is reachable from a BGP host. A route comprises an address destination, which is usually represented by an address prefix (also referred to as prefix), and information that describe the path to the address destination. The address prefix may be expressed as a combination of a network address and a mask that indicates how many bits of the address are used to identify the network portion of the address. In Internet Protocol version 4 (IPv4) addressing, for example, the address prefix can be expressed as “9.2.0.2/16”. The “/16” indicates that the first 16 bits are used to identify the unique network leaving the remaining bits in the address to identify the specific hosts within this network.
In another example, Virtual Private Network (VPN) addressing schemes may use a route distinguisher (RD) in addition to the address prefix in order to distinguish between different routes to the same address destination. For example, in a VPN address destination of “10:9.2.0.2/16”, “10” is a route distinguisher that identifies a specific VPN route to the “9.2.0.2/16” network.
The information that describes the path to the address destination in a BGP route includes, but is not limited to, an ORIGIN attribute, an AS_PATH attribute, and a NEXT_HOP attribute. The ORIGIN attribute indicates how a BGP process learned about a particular route. The value of the ORIGIN attribute for a particular route may indicate that the route was learned from an Interior Gateway Protocol (IGP), from an EGP, such as external BGP (eBGP), or that the origin of the route is unknown or learned in some other way.
The AS_PATH attribute indicates the list of autonomous systems that must be traversed in order to reach the address destination. For example, an AS_PATH attribute of “130 120” for a route indicates that the route to the address destination passes through autonomous systems 120 and 130 in that order.
The NEXT_HOP attribute for a particular route contains the address of a network element that is the next hop to the address destination. For example, the NEXT_HOP attribute for a route that is received from an eBGP peer is the network address of the eBGP peer. In another example, a PE BGP host that advertises a VPN route will include its own network address as the NEXT_HOP attribute for the VPN route it advertises.
BGP peers exchange, or advertise, routes in BGP UPDATE messages. Under the BGP-4 standard described in RFC1771, which was published by the Internet Engineering Task Force (IETF) in March 1995 and which defines the mechanism for exchanging IPv4 routes, a BGP UPDATE message includes a message header, and some or all of the following fields:
(1) Unfeasible Routes Length—the length of the Withdrawn Routes field;
(2) Withdrawn Routes—the address prefixes of the routes being withdrawn from service;
(3) Total Path Attribute Length—the length of the Path Attribute field;
(4) Path Attributes—the attributes of the routes advertised in the BGP UPDATE message including, but not limited to, the NEXT_HOP attribute, the ORIGIN attribute, and the AS_PATH attribute;
(5) Network Layer Reachability Information (NLRI)—the address prefixes of feasible routes being advertised in the BGP UPDATE message.
In BGP-4, feasible, or reachable, routes are advertised between BGP peers in a BGP UPDATE message. The BGP UPDATE message carries the address prefixes of the routes in the NLRI field of the message. The different attributes of the routes, such as the ORIGIN, NEXT_HOP, and AS_PATH attributes are carried in the Path Attribute field of the BGP UPDATE message. All routes advertised in the same BGP UPDATE message share the same path attributes.
When a BGP host determines that a particular address destination is unavailable for whatever reason, the BGP host must withdraw all routes it has advertised as reachable through this unavailable address destination. The BGP host withdraws the routes by sending a BGP UPDATE message to its BGP peers. The BGP UPDATE message includes all the address prefixes of the routes being withdrawn in the Withdrawn Routes field as <length,prefix> tuples, where <length> is the length in bits of the associated <prefix>. The Unfeasible Routes Length field of the BGP UPDATE message includes the total length of the Withdrawn Routes field. The Path Attributes field and the NLRI field are blank or not included in the message. Thus, under the BGP-4 standard, in order to withdraw the unfeasible routes, a BGP host must include in the BGP UPDATE message all of the prefixes of the routes being withdrawn.
The Exterior Border Gateway Protocol (EBGP) is widely used in network nodes, such as routers and switches, for communicating paths or routes and associated network reachability information across autonomous systems or domains. In EBGP, a node communicates, to other peer nodes in an internetwork, information about new routes or paths that the node can reach using BGP UPDATE messages. Each node builds a local route information base (RIB) that contains a complete current map of the network. If a route or path becomes unavailable, then the node removes the route from the RIB and informs other nodes using a BGP WITHDRAW message.
In some cases, a node may be authorized to send BGP WITHDRAW messages about routes that a different node (the “originator node”) originally announced in the network using a prior UPDATE message. However, BGP WITHDRAW messages do not identify originator nodes.
In a network with a large number of nodes, propagation of the BGP WITHDRAW message to all interested nodes may take a considerable period of time.
A node that receives a BGP WITHDRAW message responds by executing the well-known BGP bestpath algorithm, using the remaining paths in its route database, to select an alternate route to reach destination nodes that the router formerly could reach using the withdrawn route. While executing the bestpath algorithm, the node may generate and send one or more BGP UPDATE messages to peer nodes. However, the BGP UPDATE messages might reference paths or routes that are unreachable as a result of removal of the withdrawn route, but still present in the database of the node because of latency in propagation of the WITHDRAW message.
Once the WITHDRAW message has fully propagated, nodes that have received UPDATE messages referencing unreachable routes will reply by sending further UPDATE messages that resolve the abnormality and provide new reachability information based on loop detection and other mechanisms performed at the receiving node. Thus, a disadvantage of current practice is that propagation delays for WITHDRAW messages result in the transmission of many unnecessary UPDATE messages. Moreover, the current approach may trigger receiving nodes to perform route dampening, which involves limiting use of routes that appear to be undergoing repeated addition and withdrawal. Triggering route dampening may adversely affect the time required to perform route convergence in a BGP node.
Based on the foregoing, there is a clear need for improvements in convergence approaches in networks.
There is a particular need for a better way to process BGP WITHDRAW messages that are used to communicate inter-domain route changes.
Although the preceding description has focused on BGP in the inter-domain context as an example, the problems described above are found in other path vector protocols. Thus, there is a need to address the foregoing problems in a way that is applicable to path vector protocols other than BGP.